class Solution
{
public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<int> col(n);
        vector<int> dg(n << 1);
        vector<int> udg(n << 1);
        vector<vector<string>> ans;
        vector<string> t(n, string(n, '.'));
        function<void(int)> dfs = [&](int i) -> void
            {
                if (i == n)
                {
                    ans.push_back(t);
                    return;
                }
                for (int j = 0; j < n; ++j)
                    if (col[j] + dg[i + j] + udg[n - i + j] == 0)
                    {
                        t[i][j] = 'Q';
                        col[j] = dg[i + j] = udg[n - i + j] = 1;
                        dfs(i + 1);
                        col[j] = dg[i + j] = udg[n - i + j] = 0;
                        t[i][j] = '.';
                    }
            };
        dfs(0);
        return ans;
    }
};